public class question_42 {

}
//接雨水问题
//我的思路是研究问题的特征，直接遍历+双指针，时间复杂度应该为o(n)
class Solution_42 {
    public int trap(int[] height) {
        /*
        //这种方法是我脑筋突然想出来的
        //考虑一些特殊的情况

        int len=height.length;
        if(len==1)
            return 0;
        int sum=0;//总雨点数
        int l=0,r=1;//两个指针，l是快指针，r是慢指针
        //首先去掉两边递增的部分
        //先左边
        while (height[l]<=height[r]){
            if(r==len-1)
                return 0;//表示一整个都是递增的
            l++;
            r++;
        }
        //左边没用的已经排除了
        int start=l;
        //排除右边
        r=len-1;
        l=r-1;
        while (height[l]>=height[r]){
            if(l==0)
                return 0;//一整个都是递减的
            l--;
            r--;
        }
        int end=r;
        //两边没用的已经去掉了
        int max=height[start];
        l=start;
        for ( r = start+1; r <=end; r++) {
            if(height[r]>=max){
                for (int i = l; i <r ; i++) {
                    sum+=(height[l]-height[i]);
                }
                //更新l和max
                l=r;
                max=height[l];
            }
        }
        //然后上面大概率没有遍历完，因为end不一定是最高的那一个，所以要再加一层从右往左
        if(l!=end){//说明还需要多一层从右往左的
            //问题转变，重新设置起点了终点,这次是从右往左
            start=end;
            end=l;

            max=height[start];
            r=start;
            for ( l = start-1; l >=end ; l--) {
                if(height[l]>=max){
                    for (int i = r; i >l ; i--) {
                        sum+=(height[r]-height[i]);
                    }
                    //更新r和max
                    r=l;
                    max=height[r];
                }
            }
        }
        return sum;
         */
        //接下来使用动态规划的算法
        //思路是每一个柱子能装的水量=该柱子左边所有柱子的最高者以及右边柱子中的最高者这两者之间的最小者
        //先去掉特殊的情况
        int len=height.length;
        if(len<=2)
            return 0;
        //先获取每个柱子从左边开始到自己位置遇到的最高的柱子
        int larr[]=new int[len];
        larr[0]=0;
        for (int i = 1; i < len; i++) {
            larr[i]=larr[i-1]>height[i-1]?larr[i-1] :height[i-1];
        }
        //先获取每个柱子从右边开始到自己位置遇到的最高的柱子
        int rarr[]=new int[len];
        rarr[len-1]=0;
        for (int i = len-2; i >=0 ; i--) {
            rarr[i]=rarr[i+1]>height[i+1]?rarr[i+1]:height[i+1];
        }
        int sum=0;
        //直接循环，按照这个思路：每一个柱子能装的水量=该柱子左边所有柱子的最高者以及右边柱子中的最高者这两者之间的最小者
        //首位两个位置可以直接忽略
        for (int i = 1; i < len-1; i++) {
            int max=larr[i]>rarr[i]?rarr[i]:larr[i];//取两者中的较小者
            if(height[i]<max){
                sum+=(max-height[i]);
            }
        }
        return sum;
    }

    public static void main(String[] args) {
    }
}
